#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
vector<int> G[N];
map<int, bool> vist;
// int G[N][N];

// 从 节点开始深度优先搜索
void DFS(int x, int fa) {
  vist[x] = true;
  cout << x << " ";
  for (auto son : G[x]) {
    if (vist[son] || son == fa)
      continue;
    DFS(son, x);
  }
}

void BFS() {
  queue<int> Q;
  vist.clear();
  Q.push(1);
  vist[1] = true;
  while (!Q.empty()) {
    int fa = Q.front();
    cout << fa << " ";
    Q.pop();
    for (auto son : G[fa]) {
      if (vist[son])
        continue;
      Q.push(son);
      vist[son] = true;
    }
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    // G[b].push_back(a);
  }
  DFS(1, -1);
  cout << endl;
  BFS();
  return 0;
}